package org.zhuzx.util.pool;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.TreeSet;

import org.zhuzx.util.GeneralUtil;
import org.zhuzx.util.MicroUtil;

//@Deprecated//未测试
public class ImmutableIntMap<V> {
	
	private static final Comparator<Map.Entry<Integer,?>> mapEntryComparator = new Comparator<Map.Entry<Integer,?>>() {
		public int compare(Map.Entry<Integer, ?> o1, Map.Entry<Integer, ?> o2) {
			return o1.getKey().compareTo(o2.getKey());
		}
	};
	
	private IntMap<V> intMap;
	
	private static interface IntMap<V> {
		V get(int key);
	}
	
	private static class DirectShiftIntMap<V> implements IntMap<V> {
		private static final double SIZE_FACTOR = 3.5;
		private int offset;
		private V[] table;
		private int lastIndex;
		
		@SuppressWarnings("unchecked")
		DirectShiftIntMap(int[] keys, V[] values) {
			offset = keys[0];
			table = (V[]) Array.newInstance(values.getClass().getComponentType(), keys[keys.length-1] - offset + 1);
			for (int i = 0; i < keys.length; i++) {
				table[keys[i] - offset] = values[i];
			}
			lastIndex = table.length - 1;
		}

		public static <V> DirectShiftIntMap<V> tryConstruct(int[] keys, V[] values, int preallocationFactor) {
			int allowedSize = (int) (keys.length * preallocationFactor * SIZE_FACTOR);
			if (keys[keys.length-1] - keys[0] < allowedSize) {
				return new DirectShiftIntMap<V>(keys, values);
			} else {
				return null;
			}
		}
		
		public V get(int key) {
			int index = key - offset;
			return (index>=0 && index<=lastIndex) ? table[index] : null;
		}
	}
	
	private static class DirectRemIntMap<V> implements IntMap<V> {
		/**
		 * 经测试，当preallocationFactor为1时，元素数量必须小于等于16，找到目标尺寸的概率才能达到1%以上。
		 * preallocationFactor参数与元素数量保持固定比例同步增大时，概率会迅速上升，但需要花费更多的运算来寻找目标尺寸。
		 * 元素数量较大时，必须使用更大的分配因子才有机会构建成功，但即使成功可能也会导致极低的客座率。
		 */
		private static final int FEASIBILITY_THRESHOLD = 16;
		private static final double SIZE_FACTOR = 1.75;
		private int[] keyTable;
		private V[] valueTable;
		private int size;

		@SuppressWarnings("unchecked")
		DirectRemIntMap(int[] keys, V[] values, int size) {
			keyTable = new int[size];
			valueTable = (V[]) Array.newInstance(values.getClass().getComponentType(), size);
			for (int i = 0; i < keys.length; i++) {
				int index = keys[i] % size;
				keyTable[index] = keys[i] / size;
				valueTable[index] = values[i];
			}
			this.size = size;
		}
		
		public static <V> DirectRemIntMap<V> tryConstruct(int[] keys, V[] values, int preallocationFactor) {
			int size = keys.length;
			if (size / preallocationFactor > FEASIBILITY_THRESHOLD) return null;
			int allowedSize = (int) (size * preallocationFactor * SIZE_FACTOR);
			outer:
			for (; size <= allowedSize; size++) {
				boolean[] test = new boolean[size];
				for (int i = 0; i < keys.length; i++) {
					int index = keys[i] % size;
					if (index < 0) {
						index = -index - 1;
					}
					if (test[index]) {
						continue outer;
					} else {
						test[index] = true;
					}
				}
				return new DirectRemIntMap<V>(keys, values, size);
			}
			return null;
		}

		public V get(int key) {
			int index = (key < 0) ? (-(key % size) - 1) : (key % size);
			return (key/size == keyTable[index]) ? valueTable[index] : null;
		}
	}
	
	/**
	 * 完全不能辨别外来非key值，会被其冒充key值取得value值。
	 * 虽然可以另外用数组保存高位低位验证是否key值，但代价太大，还不如链表。
	 */
	private static class MultipleShiftIntMap<V> implements IntMap<V> {
		private static final double SIZE_FACTOR = 3.5;
		private V[] table;
		private int remQuotient;
		private int divQuotient;
		private int offset;
		private int lastIndex;
		
		@SuppressWarnings("unchecked")
		MultipleShiftIntMap(int[] keys, V[] values, int start, int length, int min, int max) {
			int maxLength = String.valueOf(keys[keys.length-1]).length();
			remQuotient = 10 * start;//对高位取余
			divQuotient = 10 * (maxLength - (start + length));//对低位整除
			offset = min;
			table = (V[]) Array.newInstance(values.getClass().getComponentType(), max - min + 1);
			for (int i=0; i<keys.length; i++) {
				table[shift(keys[i])] = values[i];
			}
			lastIndex = table.length - 1;
		}
		
		private int shift(int key) {
			if (remQuotient > 0) {
				key = key % remQuotient;
			}
			if (divQuotient > 0) {
				key = key / divQuotient;
			}
			if (offset > 0) {
				key = key - offset;
			}
			return key;
		}

		@Deprecated//对于正负数同时存在的情况，是否处理有误？
		public static <V> MultipleShiftIntMap<V> tryConstruct(int[] keys, V[] values, int preallocationFactor) {
			int size = keys.length;
			int allowedSize = (int) (size * preallocationFactor + SIZE_FACTOR);
			String[] keyStrs = new String[size];
			int maxLength = Math.max(String.valueOf(keys[0]).length(),
					String.valueOf(keys[size-1]).length());
			for (int i=0; i<size; i++) {
				String keyStr = String.valueOf(keys[i]);
				String filler = MicroUtil.createRepeatedCharSequence('0', maxLength-keyStr.length());
				keyStrs[i] = (keyStr.charAt(0) == '-') ? ("-" + filler + keyStr.substring(1)) : (filler + keyStr);
			}
			int indexLength = String.valueOf(allowedSize).length();
			int lastStartIndex = maxLength - indexLength;
			for (int start = 0; start <= lastStartIndex; start++) {
				for (int length = 1; length <= indexLength; length++) {
					TreeSet<String> counter = new TreeSet<>();
					for (String key : keyStrs) {
						counter.add(key.substring(start, length));
					}
					if (counter.size() == size) {
						int min = Integer.parseInt(counter.first());
						int max = Integer.parseInt(counter.last());
						if (max - min < allowedSize) {//@Deprecated//未寻找最优情况
							return new MultipleShiftIntMap<V>(keys, values, start, length, min, max);
						}
					}
				}
			}
			return null;
		}
		
		public V get(int key) {
			int index = shift(key);
			return (index <= lastIndex) ? table[index] : null;
		}
	}
	
	private static class LinkedRemIntMap<V> implements IntMap<V> {
		private static final int MAXIMUM_CAPACITY = 1 << 30;
		private static final int LINK_THRESHOLD = 8;
		private SearchableSet<V>[] table;
		private int lastIndex;
		private int[] specificKeys;
		private V[] specificValues;
		
		private static interface SearchableSet<V> {
			public V search(int key);
		}
		
		private static class Entry<V> implements SearchableSet<V> {
			int key;
			V value;
			Entry<V> next;
			Entry(int key, V value, Entry<V> next) {
				this.key = key;
				this.value = value;
				this.next = next;
			}
			public V search(int key) {
				if (key == this.key) {
					return this.value;
				} else {
					Entry<V> e = next;
					while (e != null) {
						if (key == e.key) {
							return e.value;
						}
						e = e.next;
					}
					return null;
				}
			}
		}
		
		private class SharedArraySection implements SearchableSet<V> {
			int fromIndex;
			int toIndex;
			SharedArraySection(Entry<V> head, int fromIndex, int length) {
				Entry<V> e = head;
				int index = fromIndex + length - 1;//无需排序，构造Map时传入的数组是正序的，所以每个桶内的链表都是倒序的（后来居上）。
				while (e != null) {
					specificKeys[index] = e.key;
					specificValues[index] = e.value;
					e = e.next;
					index--;
				}
				this.fromIndex = fromIndex;
				this.toIndex = fromIndex + length;
			}
			public V search(int key) {
				int index = Arrays.binarySearch(specificKeys, fromIndex, toIndex, key);
				return (index < 0) ? null : specificValues[index];
			}
		}
		
		@SuppressWarnings("unchecked")
		public LinkedRemIntMap(int[] keys, V[] values, int preallocationFactor) {
			int elemNum = keys.length;
			int tableSize = tableSizeFor(elemNum * preallocationFactor);
			table = new SearchableSet[tableSize];
			for (int i = 0; i < elemNum; i++) {
				int index = indexOf(keys[i]);
				table[index] = new Entry<V>(keys[i], values[i], (Entry<V>) table[index]);
			}
			specificKeys = new int[elemNum];
			specificValues = (V[]) Array.newInstance(values.getClass().getComponentType(), elemNum);
			int cursor = 0;
			for (int i = 0; i < table.length; i++) {
				Entry<V> e = (Entry<V>) table[i];
				int count = 0;
				while (e != null) {
					count++;
					e = e.next;
				}
				if (count > LINK_THRESHOLD) {
					SharedArraySection section = new SharedArraySection((Entry<V>) table[i], cursor, count);
					table[i] = section;
					cursor = section.toIndex;
				}
			}
			if (cursor < specificKeys.length) {
				int[] suitableSizeKeys = new int[cursor];
				System.arraycopy(specificKeys, 0, suitableSizeKeys, 0, cursor);
				specificKeys = suitableSizeKeys;
				V[] suitableSizeValues = (V[]) Array.newInstance(values.getClass().getComponentType(), cursor);
				System.arraycopy(specificValues, 0, suitableSizeValues, 0, cursor);
				specificValues = suitableSizeValues;
			}
		}
		
		private int indexOf(int key) {
			return (key ^ (key >>> 16)) & lastIndex;
		}
		
		private static final int tableSizeFor(int cap) {
			int n = cap - 1;
			n |= n >>> 1;
			n |= n >>> 2;
			n |= n >>> 4;
			n |= n >>> 8;
			n |= n >>> 16;
			return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
		}
		
		public V get(int key) {
			SearchableSet<V> set = table[indexOf(key)];
			return (set == null) ? null : set.search(key);
		}
	}
	
	public ImmutableIntMap(Map<Integer,V> originalMap, int preallocationFactor, boolean willUseStrictKey) {
		if (GeneralUtil.isEmpty(originalMap)) {
			throw new IllegalArgumentException("originalMap不可为空");
		}
		if (originalMap.containsKey(null)) {
			throw new IllegalArgumentException("originalMap不可包含空键");
		}
		if (preallocationFactor < 1) {
			throw new IllegalArgumentException("preallocationFactor不可小于1");
		}
		V value = null;
		for (V v : originalMap.values()) {
			if (v != null) {
				value = v;
				break;
			}
		}
		if (value == null) {
			throw new IllegalArgumentException("originalMap不可全部为空值");
		}
		TreeSet<Map.Entry<Integer,V>> treeSet = new TreeSet<>(mapEntryComparator);
		treeSet.addAll(originalMap.entrySet());
		int size = treeSet.size();
		int[] keys = new int[size];
		Class<?> cla = value.getClass();
		@SuppressWarnings("unchecked")
		V[] values = (V[]) Array.newInstance(cla, size);
		int index = 0;
		for (Map.Entry<Integer, V> entry : treeSet) {
			keys[index] = entry.getKey();
			values[index] = entry.getValue();
			index++;
		}
		intMap = DirectShiftIntMap.tryConstruct(keys, values, preallocationFactor);
		if (intMap == null) {
			intMap = DirectRemIntMap.tryConstruct(keys, values, preallocationFactor);
		}
		if (intMap == null && willUseStrictKey) {
			intMap = MultipleShiftIntMap.tryConstruct(keys,values, preallocationFactor);
		}
		if (intMap == null) {
			intMap = new LinkedRemIntMap<V>(keys, values, preallocationFactor);
		}
	}
	
	public ImmutableIntMap(Map<Integer,V> originalMap) {
		this(originalMap, 1, false);
	}
	
	public V get(int key) {
		return intMap.get(key);
	}

}